跳转到内容

DLOGTIME

维基百科,自由的百科全书

複雜度理論內,DLOGTIME是一個複雜度類,其問題可以用決定型圖靈機,在對數成長的時間內解決。這是使用決定型時間,所能定義出最小且非單純(non-trivial)的複雜度類。這類複雜度一定使用隨機存取圖靈機來定義,因為機器沒有足夠的時間來讀取整個輸入(輸入的大小,成長率是O(n))。

DLOGTIME-均一性(uniformity)在電路複雜性裡面是很重要的。

詢問輸入字串的長度這個問題屬於DLOGTIME,因為我們可以對可能的輸入大小進行折半搜索演算法(binary search)。